package com.torlesse.leetcode.algorithm.shuzu;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: torlesse-liang
 * @Date: 2022/03/07/22:35
 * @Description: 删除排序数组的重复项
 */
public class RemoveDuplicates {

    public static void main(String[] args) {
        int[] array = {1,1,2};
        System.out.println(removeDuplicates(array));
        for (int i = 0; i < removeDuplicates(array); i++) {
            System.out.print(array[i]);
        }
    }

    /**
     * 题目：给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     * 示例1：
     * 输入：nums = [1,1,2]
     * 输出：2, nums = [1,2]
     *
     *
     *
     * 思想：有序数组，比较去重
     * 数组：1,1,1,2,2,3,4,5
     * 过程：i=1  i从开始比较 ,array[i] == array[i-1]? (pos++):array[i-pos] = array[i];
     * 目标：1,2,3,4,5
     *
     */
    public static int removeDuplicates(int[] array){
        int pos = 0;
        for (int i = 1; i < array.length; i++) {
            if(array[i] == array[i-1]){
                pos ++;
            }else {
                array[i-pos] = array[i];
            }
        }
        return array.length - pos;
    }
}
